Formal language

This is a set of words over an alphabet, i.e. L \subseteq \sum^*.

Alphabet

A finite, non-empty set of characters which is commonly denoted as: \sum.

Examples of such Alphabets are:

• \sum := \{0,1\}
• \sum := \{a,b,c\}

\sum^n is a shorthand that gets defined as \{ w | \text{where w is a word over} \sum, w = n, n \in \mathbb{N}_0 \}. With \sum := \{a,b,c\} the following holds:

• \sum^0 = e
• \sum^1 = \{ a, b, c \}
• \sum^2 = \{ aa, ab, ac, ba, bb, bc, ca, cb, cc \}

Furthermore there are two common notations that include/exclude the neutral element explicitly: \sum^* = \sum^+ \cap \{e\}

Word

A finite sequence of characters from an Alphabet.

e describes the sequence without characters. See neutral element. w^R is the word in reverse order.

Examples of such Words are:

• 0: Word over \{0,1\}
• hello \ world: Word over \{ \ ,a,b,c,\dots,z \}